/**
 * 面试题 17.06. 2出现的次数
 * https://leetcode-cn.com/problems/number-of-2s-in-range-lcci/
 */
public class Solutions_mianshi_17_06 {
    public static void main(String[] args) {
//        int n = 25;  // output: 9
        int n = 2;  // output: 1
//        int n = 1_000_000_000;  // output: 900000000
        int result = numberOf2sInRange(n);
        System.out.println(result);
    }

    /**
     * 解题思路：[1, n] 中，2 出现的次数
     * 等于数字 n 中个位上 2 最多出现的次数 + 十位上 2 最多出现的次数 + ...
     * 以 25 为例
     * 计算个位：
     *      标准部分：25 / 10 = 2，最多出现 2 * 1 = 2 个数字 2
     *      额外部分：25 % 10 = 5，5 >= 2，最多出现 1 个数字 2
     * 计算十位：
     *      标准部分：25 / 100 = 0，最多出现 0 * 10 = 0 个数字 2
     *      额外部分：25 % 100 = 25，25 >= 20，最多出现 6 个数字 2，即 20,21,22,23,24,25
     * 最终结果为 2 + 1 + 6 = 9
     */
    public static int numberOf2sInRange(int n) {
        int res = 0;
        for (int i = 1; i <= n; i *= 10) {
            // 若要取个位，需要 % 10，取十位，则需要 % 100
            long j = i * 10;
            // 标准部分
            long cnt = n / j * i;
            // 额外部分
            long temp = Math.max(0, n % j - 2 * i + 1);
            long remind = Math.min(temp, i);
            res += cnt + remind;
        }
        return res;
    }
}
